package com.zjj.algorithm.learning.leetcode.str;

/**
 * 14. 最长公共前缀 简单题
 * <p>
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * <p>
 * 如果不存在公共前缀，返回空字符串 ""。
 * <p>
 * 示例 1：
 * <p>
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 示例 2：
 * <p>
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 解释：输入不存在公共前缀。
 *
 * @author zjj_admin
 * @date 2022/11/24 15:48
 */
public class LongestCommonPrefix {

    public static void main(String[] args) {
        String[] strs = new String[]{"flower", "flow", "flight"};
        String res = longestCommonPrefix2(strs);
        System.out.println("res = " + res);
    }

    /**
     * 自己写的
     * 时间
     * 1 ms
     * 击败
     * 68.97%
     * 内存
     * 40.9 MB
     * 击败
     * 6.46%
     * 思路：
     * 先找到最小的字符串长度
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix1(String[] strs) {
        StringBuilder res = new StringBuilder();
        int minLen = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            if (minLen > strs[i].length()) {
                minLen = strs[i].length();
            }
        }
        for (int i = 0; i < minLen; i++) {
            String strI = strs[0].substring(i, i + 1);
            for (int j = 0; j < strs.length; j++) {
                if (!strI.equals(strs[j].substring(i, i + 1))) {
                    return res.toString();
                }
            }
            res.append(strI);
        }
        return res.toString();
    }


    /**
     * 别人写的，太牛皮了
     *
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 39.7 MB
     * 击败
     * 24.2%
     *
     * @param strs
     * @return
     */
    public static String longestCommonPrefix2(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        //公共前缀比所有字符串都短，随便选一个先
        String s = strs[0];
        for (String string : strs) {
            while (!string.startsWith(s)) {
                //公共前缀不匹配就让它变短！
                s = s.substring(0, s.length() - 1);
            }
        }
        return s;
    }


}
